#include <vector>
#include <algorithm>

using namespace std;

// 31. 下一个排列
class Solution1
{
public:
    void nextPermutation(vector<int>& nums) 
    {
        int i = nums.size() - 2;
        while(i >= 0 && nums[i] >= nums[i + 1]) --i;

        int j = nums.size() - 1;
        if(i >= 0)
        {
            while(j >= 0 && nums[j] <= nums[i]) --j;
            swap(nums[i], nums[j]);
        }
        reverse(nums.begin() + i + 1, nums.end());
    }
};

// 287. 寻找重复数
class Solution2
{
public:
    int findDuplicate(vector<int>& nums) 
    {
        int n = nums.size();
        for(int i = 0; i < n; ++i)
        {
            int num = abs(nums[i]);
            if(nums[num] < 0) return num;
            else nums[num] *= -1;
        }
        return -1;
    }
};

// 72. 编辑距离
class Solution3
{
public:
    int minDistance(string word1, string word2) 
    {
        int m = word1.size(), n = word2.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        for(int i = 0; i <= m; ++i) dp[i][0] = i;
        for(int j = 1; j <= n; ++j) dp[0][j] = j;

        for(int i = 1; i <= m; ++i)
        {
            for(int j = 1; j <= n; ++j)
            {
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1;
                if(word1[i - 1] == word2[j - 1])
                    dp[i][j] = min(dp[i][j], dp[i - 1][j - 1]);
                else
                    dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + 1);
            }
        }
        return dp[m][n];
    }
};

// 300. 最长递增子序列
class Solution4
{
public:
    int lengthOfLIS(vector<int>& nums) 
    {
        vector<int> g;
        for(int x : nums)
        {
            // lower_bound 返回第一个大于或等于 x 的元素的位置
            auto it = lower_bound(g.begin(), g.end(), x);
            if(it == g.end()) g.push_back(x);
            else *it = x;
        }
        return g.size();
    }
};